package com.test.daily.leetcode.y2022.m07.day0719.v04;

import com.sun.xml.internal.ws.client.sei.ResponseBuilder;

import java.util.ArrayList;
import java.util.List;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/19 下午 03:07
 * @version: 1.0
 */
public class Solution {
    public static class Node{
        Node left;
        Node right;
        int value;
        public Node(int value){
            this.value = value;
        }
    }
    public static Node BSTNode(Node head){
        if(BSTSize(head) != 0){
            return head;
        }
        int leftAns = BSTSize(head.left);
        int rightAns = BSTSize(head.right);
        return leftAns > rightAns ? head.left : head.right;

    }
    public static int BSTSize(Node head){
        List<Node> list = new ArrayList<>();
        in(head, list);
        for (int i = 1; i < list.size(); i++) {
            if(list.get(i).value<= list.get(i-1).value){
                return 0;
            }
        }
        return list.size();
    }
    public static void in(Node head, List<Node> list){
        if(head == null){
            return;
        }
        if (head.left != null){
            list.add(head.left);
        }
        list.add(head);
        if(head.right != null){
            list.add(head.right);
        }
    }

    public static class Info{
        public int min;
        public int max;
        public Node ans;
        public int maxSize;
        public Info(int min, int max, Node ans, int maxSize){
            this.min = min;
            this.max = max;
            this.ans = ans;
            this.maxSize = maxSize;
        }
    }

    public Node maxBST(Node head){
        return process(head).ans;
    }
    public Info process(Node head){
        if(head == null){
            return null;
        }
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        int min = head.value;
        int max = head.value;
        Node ans = null;
        int maxSize = 0;
        if(leftInfo != null){
            min = Math.min(leftInfo.min, min);
            max = Math.max(leftInfo.max, max);
            if(leftInfo.maxSize > maxSize){
                ans = leftInfo.ans;
                maxSize = leftInfo.maxSize;
                ans = leftInfo.ans;
            }
            if(rightInfo != null){
                min = Math.min(rightInfo.min, min);
                max = Math.max(rightInfo.max, max);
                if(rightInfo.maxSize > maxSize){
                    ans = rightInfo.ans;
                    maxSize = rightInfo.maxSize;
                    ans = rightInfo.ans;
                }
            }
            if(leftInfo == null? true: leftInfo.ans == head.left && leftInfo.max < head.value
               && rightInfo == null? true: rightInfo.ans == head.right && rightInfo.min > head.value){
                ans = head;
                maxSize = (leftInfo == null ? 0: leftInfo.maxSize)
                        + (rightInfo == null ? 0: rightInfo.maxSize)
                        + 1;
            }
        }
        return new Info(min, max, ans,maxSize);
    }

}
